package com.lsa.letcode.the15.the3sum;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public List<List<Integer>> threeSum(int[] num) {
    	return twoPointers(num);
    }
    
//    @SuppressWarnings("unused")
	private  List<List<Integer>> twoPointers(int[] num) {
    	Arrays.sort(num);
    	
    	List<List<Integer>> res3s = new ArrayList<List<Integer>>();
    	
    	{
    		int j = num.length - 1;
    		int i = j - 1;
    		while(i > - 1 && num[i] == num[j] && (i > 0 && num[i - 1] == num[j])) {
				i--;
			}
    		
    		int prevLeft = i > -1? num[i] : -1; 
    		
    		while(i > - 1) {
    			int l = num[i];
				int r = num[j];
				
				int target = -(l + r);
				if (j - i > 1) { // length of interval to search in
					int idx = Arrays.binarySearch(num, i + 1, j, target);
					if (idx > -1) {
						boolean isContains = false;
						if (res3s.size() > 0 ){
							List<Integer> lst = res3s.get(res3s.size() - 1);
							isContains = lst.get(0) == l && lst.get(1) == num[idx] && lst.get(2) == r;
						}
						if (!isContains) {
							res3s.add(Arrays.asList(l, num[idx], r));
						}
					}
				}
				
				// try move left pointer to the left
    			// stop if num[i] != prevLeft OR num[i] == prevLeft but it is the last el with this property
    			--i;
    			while(i > - 1 && num[i] == prevLeft && (i > 0 && num[i - 1] == prevLeft)  ) {
    				i--;
    			}
    			
    			if (i == -1) {
    				int oldJ = j; 
    				// try move right pointer to the left
    				// stop if num[i] != prevRight
    				j--;
    				while(j > - 1 && num[j] == num[oldJ]) {
    					j--;
    				}
    				if (j == -1) {
    					break;
    				}
    				// try move left pointer to the left from the recently moved right pointer
        			// stop if num[i] != num[j] OR num[i] == num[j] but it is the last el with this property
    				// the latter condition is include to handle 0,0,0 ... 0 cases
    				i = j - 1;
    				while(i > - 1 && num[i] == num[j] && (i > 0 && num[i - 1] == num[j])) {
    					i--;
    				}
    				if (i == -1) {
    					break;
    				}
    			}
    			
    			if (i > -1) {
    				prevLeft = num[i];
    			}
    		}
    	}
    	
    	return res3s;
    }

//    @SuppressWarnings("unused")
//	private List<List<Integer>> reductionTo2Sum(int[] num) {
//		Arrays.sort(num);
//    	
//    	List<List<Integer>> res3s = new ArrayList<List<Integer>>();
//    	
//    	for (int i = 0; i < num.length; i++) {
//    		List<List<Integer>> res2s = twoSum(num, i+1, num.length - 1, -num[i]);
//    		for (List<Integer> res2 : res2s) {
//    			List<Integer> res3 = cons(num[i], res2);
//    			int idx = Collections.binarySearch(res3s, res3, new Comparator<List<Integer>>() {
//        			@Override
//        			public int compare(List<Integer> o1, List<Integer> o2) {
//        				for (int j = 0; j < 3; j++) {
//							int n1 = o1.get(j);
//							int n2 = o2.get(j);
//							int res = n1 - n2;
//							if (res != 0) {
//								return res;
//							}
//						}
//        				return 0;
//        			}
//        		});
//    			if (idx < 0) {
//					res3s.add(res3);
//    			}
//			}
//		}
//    	
//        return res3s;
//	}
//    
//    private List<Integer> cons(final int n, final List<Integer> l) {
//    	return new AbstractList<Integer>() {
//			@Override
//			public Integer get(int i) {
//				if (i == 0) {
//					return n;
//				}
//				return l.get(i - 1);
//			}
//
//			@Override
//			public int size() {
//				return 1 + l.size();
//			}
//
//			@Override
//			public String toString() {
//				StringBuilder sb = new StringBuilder();
//				sb.append('{');
//				sb.append(n);
//				for (Integer i : l) {
//					sb.append(',');
//					sb.append(i);
//				}
//				sb.append('}');
//				return sb.toString();
//			}
//		};
//    }
//    
//    private List<List<Integer>> twoSum(int[]num, int from, int to, int target) {
//    	List<List<Integer>> res2s = new ArrayList<List<Integer>>();
//    	for (int i = from; i <= to; i++) {
//			int a = num[i];
//			int b = target - a;
//			if (i+1 <= to) {
//				int idx = Arrays.binarySearch(num, i+1, to+1, b);
//				if (idx > -1) {
//					res2s.add(Arrays.asList(a, num[idx]));
//				}
//			}
//		}
//    	return res2s;
//    }
}
